#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<stack>
using namespace std;

class Node{
public:
    Node(int value){
        this->value = value;
    }
    bool operator<(Node* b){
       return this->value<b->value;
    }
public:
    int value;
};



class Solution {
public:
    
    int findCircleNum(vector<vector<int>>& isConnected) {
        int size = isConnected[0].size();
        for(int i = 0;i<size;++i){
            Node* node = new Node(i);
            M.insert(make_pair(i,node));
            parent.insert(make_pair(node,node));
        }
        for(int i = 0;i<isConnected.size();++i){
            for(int k = 0;k<isConnected[i].size();++k){
            int a = isConnected[i][k];
            if(a==1){
                if(!isSameSet(i,k)){
                    unionSet(i,k);
                }
            }
        }
        }
        set<Node*> S;
        for(int j = 0;j<M.size();++j){
            S.insert(findFather(M[j]));
        }
        return S.size();    
    }
        
    Node* findFather(Node* a){
        stack<Node*> path;
        while(parent[a]!=a){
            path.push(a);
            a = parent[a];
        }
        while(!path.empty()){
            Node* b = path.top();
            path.pop();
            parent[b] = a;
        }
        return a;
    }

    bool isSameSet(int a,int b){
        if(M.find(a)==M.end()||M.find(b)==M.end()){
            return false;
        }
        return findFather(M[a])==findFather(M[b]);
    }

    void unionSet(int a,int b){
        if(this->M.find(a)==this->M.end()||this->M.find(b)==this->M.end()){
            return;
        }
        Node* afather = findFather(M[a]);
        Node* bfather = findFather(M[b]);
        if(afather!=bfather){
            parent[afather] = bfather;
        }
    }
public:
    map<int,Node*> M;
    map<Node*,Node*> parent;
};